#include "../tools.h"

// 合并相邻有序数列
void MergeArr(vector<int>& arr, int l, int m, int r, vector<int>& tmp)
{
    int l_end = m + 1, r_end = r + 1;
    int p = l, p_l = l, p_r = m + 1;
    while (p_l < l_end && p_r < r_end)
    {
        if (arr[p_l] < arr[p_r]) tmp[p++] = arr[p_l++];
        else tmp[p++] = arr[p_r++];
    }
    while (p_l < l_end) tmp[p++] = arr[p_l++];
    while (p_r < r_end) tmp[p++] = arr[p_r++];

    for (int i = l; i < r + 1; ++i)
        arr[i] = tmp[i];
}

void Merge_Sort(vector<int>& arr, int l, int r, vector<int>& tmp)
{
    if (l >= r) return; // ! = 否则栈越界，已经无法拆分

    // 拆分
    int m = (l + r) / 2;
    Merge_Sort(arr, l, m, tmp);
    Merge_Sort(arr, m + 1, r, tmp);

    // 合并相邻有序数列
    MergeArr(arr, l, m, r, tmp);
}

int main(int argc, char const *argv[])
{
    vector<int> arr = {6, 2, 1, 7, 9, 3, 4, 5, 10, 8};
    show(arr);
    vector<int> tmp(arr.size(), 0);

    Merge_Sort(arr, 0, arr.size() - 1, tmp);
    show(arr);



    return 0;
}
